package pers.lls.hds.sort.shell;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * 对无序序列反复的进行拆分并且对拆分后的序列使用插入排序的一种算法
 * 基于插入排序实现，时间复杂度为O(N*logN)
 * 最坏和平均执行效率相差不大
 * 代码实现简短、简单
 *
 * @author lilichai
 */
public class ShellSort {

    public void shellSort(long[] arr) {
        int size = arr.length;
        int inner, outer;
        long temp;
        int h = 1;
        while (h <= size / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            for (outer = h; outer < size; outer++) {
                temp = arr[outer];
                inner = outer;
                while (inner > h - 1 && arr[inner - h] >= temp) {
                    arr[inner] = arr[inner - h];
                    inner -= h;
                }
                arr[inner] = temp;
            }
            h = (h - 1) / 3;
        }
    }

    public static void main(String[] args) {
        ShellSort sort = new ShellSort();
        long[] arr = {1, 3, 6, 7, 2, 4};
        sort.shellSort(arr);
        Arrays.stream(arr).forEach(d -> System.out.print("  " + d));
    }

}

